/// @tags: DivGraph
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

namespace BlueQuantum {

int const N = 1e2 + 5;

int n, m, e_cnt;
int d[N][N], vis[N], match[N], heads[N];
bool avi[N], abl[N], out[N];

bool dfs(int x) {
  for (int i = 1; i <= n; ++i)
    if (avi[i] && d[x][i] && !vis[i]) {
      vis[i] = true;
      if (!match[i] || dfs(match[i])) return match[i] = x, true;
    }
  return false;
}

inline int main() {
  cin >> n >> m;
  for (int i = 1, u, v; i <= m; ++i) {
    cin >> u >> v;
    d[u][v] = true;
  }
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) d[i][j] |= d[i][k] && d[k][j];
  for (int i = 1; i <= n; ++i) d[i][i] = false, avi[i] = true;
  int ans = n;
  for (int i = 1; i <= n; ++i) ans -= dfs(i), memset(vis, 0, sizeof(vis));
  cout << ans << '\n';
  for (int i = 1; i <= n; ++i) vis[match[i]] = true;
  vector<int> s;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) s.push_back(i);
  memset(vis, 0, sizeof(vis));
  bool flag = true;
  while (flag) {
    flag = false;
    for (vector<int>::iterator i = s.begin(); i != s.end(); ++i)
      for (int y = 1; y <= n; y++)
        if (d[*i][y]) vis[y] = 1;
    for (vector<int>::iterator i = s.begin(); i != s.end(); ++i)
      if (vis[*i]) {
        flag = true;
        while (vis[*i]) *i = match[*i];
      }
  }
  for (vector<int>::iterator i = s.begin(); i != s.end(); ++i) out[*i] = true;
  for (int i = 1; i <= n; ++i) cout << (out[i] ? '1' : '0');
  cout << '\n';
  for (int i = 1; i <= n; ++i) {
    memset(match, 0, sizeof(match));
    avi[i] = false;
    int tmp = n;
    for (int j = 1; j <= n; ++j)
      if (d[i][j] || d[j][i]) avi[j] = false, tmp--;
    for (int i = 1; i <= n; ++i)
      if (avi[i]) tmp -= dfs(i), memset(vis, 0, sizeof(vis));
    if (tmp == ans) abl[i] = true;
    memset(avi, true, sizeof(avi));
  }
  for (int i = 1; i <= n; ++i) cout << (abl[i] ? '1' : '0');
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4298 [CTSC2008] 祭祀.in", "r", stdin);
  freopen("P4298 [CTSC2008] 祭祀.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
